<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Tutorials - AIB</title>
  

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Tutorials - AIB
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
</li>
<li><a href="tut.html">Tutorials</a>
<ul>
<li><a href="sift.html">SIFT</a>
</li>
<li><a href="dsift.html">DSIFT/PHOW</a>
</li>
<li><a href="mser.html">MSER</a>
</li>
<li><a href="ikm.html">IKM</a>
</li>
<li><a href="hikm.html">HIKM</a>
</li>
<li><a href="aib.html" class='active' >AIB</a>
</li>
<li><a href="quickshift.html">Quick shift</a>
</li>
<li><a href="slic.html">SLIC</a>
</li>
<li><a href="kdtree.html">kd-tree</a>
</li>
<li><a href="imdisttf.html">Distance transf.</a>
</li>
<li><a href="utils.html">Utils</a>
</li>
</ul></li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
      

<p>The <b>Agglomerative Information Bottleneck (AIB)</b> algorithm
greedily compresses discrete data by iteratively merging the two
elements which cause the mutual information between the data and the
class labels to decreases as little as possible.</p>

<p>Here we test AIB on the problem of finding a discriminatively
optimal quantization of a mixture of Gaussians. The data in this case
is 2 dimensional:</p>

<div class="figure">
<image src="../demo/aib_basic_data.jpg"></image>
<div class="caption">
<span class="content">
Random data generated from a Gaussian mixture with three components
(class labels are indicated by color).
</span>
</div>
</div>

<p>We quantize this data on a fixed lattice (a 20x20 grid shown in the
figures below), and construct histograms for each class.</p>

<div class="highlight"><pre><span class="n">f1</span> <span class="p">=</span> <span class="n">quantize</span><span class="p">(</span><span class="n">X1</span><span class="p">,</span><span class="n">D</span><span class="p">,</span><span class="n">K</span><span class="p">)</span> <span class="p">;</span>
<span class="n">f2</span> <span class="p">=</span> <span class="n">quantize</span><span class="p">(</span><span class="n">X2</span><span class="p">,</span><span class="n">D</span><span class="p">,</span><span class="n">K</span><span class="p">)</span> <span class="p">;</span>
<span class="n">f3</span> <span class="p">=</span> <span class="n">quantize</span><span class="p">(</span><span class="n">X3</span><span class="p">,</span><span class="n">D</span><span class="p">,</span><span class="n">K</span><span class="p">)</span> <span class="p">;</span>

<span class="n">Pcx</span><span class="p">(</span>1<span class="p">,:)</span> <span class="p">=</span> <span class="n">vl_binsum</span><span class="p">(</span><span class="n">Pcx</span><span class="p">(</span>1<span class="p">,:),</span> <span class="nb">ones</span><span class="p">(</span><span class="nb">size</span><span class="p">(</span><span class="n">f1</span><span class="p">)),</span> <span class="n">f1</span><span class="p">)</span> <span class="p">;</span>
<span class="n">Pcx</span><span class="p">(</span>2<span class="p">,:)</span> <span class="p">=</span> <span class="n">vl_binsum</span><span class="p">(</span><span class="n">Pcx</span><span class="p">(</span>2<span class="p">,:),</span> <span class="nb">ones</span><span class="p">(</span><span class="nb">size</span><span class="p">(</span><span class="n">f2</span><span class="p">)),</span> <span class="n">f2</span><span class="p">)</span> <span class="p">;</span>
<span class="n">Pcx</span><span class="p">(</span>3<span class="p">,:)</span> <span class="p">=</span> <span class="n">vl_binsum</span><span class="p">(</span><span class="n">Pcx</span><span class="p">(</span>3<span class="p">,:),</span> <span class="nb">ones</span><span class="p">(</span><span class="nb">size</span><span class="p">(</span><span class="n">f3</span><span class="p">)),</span> <span class="n">f3</span><span class="p">)</span> <span class="p">;</span>
</pre></div>


<p>Next we apply AIB:</p>

<div class="highlight"><pre><span class="p">[</span><span class="n">parents</span><span class="p">,</span> <span class="n">cost</span><span class="p">]</span> <span class="p">=</span> <span class="n">vl_aib</span><span class="p">(</span><span class="n">Pcx</span><span class="p">)</span> <span class="p">;</span>
</pre></div>


<p>This provides us with a list of parents of each column
in <code>Pcx</code>, forming a tree of merges. We can now &quot;cut&quot; this
tree to obtain any number of clusters.</p>

<div class="figure">
<image src="../demo/aib_basic_clust_2.jpg"></image>
<image src="../demo/aib_basic_clust_3.jpg"></image>
<image src="../demo/aib_basic_clust_4.jpg"></image>
<div class="caption">
<span class="content">
Three &quot;cuts&quot; of the merge tree, showing 10, 3, and 2 clusters. The
gray squares are nodes of the tree which did not have any data points
which were quantized to them.
</span>
</div>
</div>

<p>Notice that the resulting clusters do not have to be contiguous in
the original space.</p>


   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 